package com.atcumt.Carl.Dfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 组合问题：N个数里面按一定规则找出k个数的集合
 * 切割问题：一个字符串按一定规则有几种切割方式
 * 子集问题：一个N个数的集合里有多少符合条件的子集
 * 排列问题：N个数按一定规则全排列，有几种排列方式
 * 棋盘问题：N皇后，解数独等等
 */
public class Dfs01 {

    /**
     * 组合
     * 已选择的元素个数：path.size();
     * 需要的元素个数为: k - path.size();
     * 剪枝: 至多从 n - (k - path.size()) + 1 遍历
     */
    List<List<Integer>> res = new ArrayList<>(); // 存放符合条件的结果集
    List<Integer> path = new ArrayList<>(); // 存放符合条件的单一结果

    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return res;
    }

    private void combineHelper (int n, int k, int start) {

        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return; // 终止条件
        }

        for (int i = start; i < n - (k - path.size()) + 1; i++) {
            path.add(i);
            combineHelper(n, k, i + 1);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 组合总和:元素可重复
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        combinationSum3Helper(k, n, 1, 0);
        return res;
    }

    private void combinationSum3Helper(int k, int n, int start, int sum) {

        if (path.size() == k) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
                return; // 终止条件
            }
        }

        if (sum > n) {
            return; // 剪枝
        }

        // 只能取 1 - 9
        for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            sum += i;
            combinationSum3Helper(k, n, i + 1, sum);
            path.remove(path.size() - 1);
            sum -= i; // 递归过程每次做完选择要撤销
        }
    }

    /**
     * 组合总和Ⅱ：每个数字只能使用一次，不可重复。
     * 同一树枝上的元素不用去重，同一树层上的需要去重，用 target 减元素更快
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSum2Helper(candidates, target, 0);
        return res;
    }

    private void combinationSum2Helper (int[] candidates, int target, int start) {

        if (target == 0) {
            res.add(new ArrayList<>(path));
            return; // 终止条件
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break; // 剪枝
            }

            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }

            path.add(candidates[i]);
            combinationSum2Helper(candidates, target - candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }

}
